#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN=126;
const ll MOD=9999991;
ll dp[MAXN][MAXN];
void Init() {
	int len=MAXN-1;
	for (int i=0; i<=len; ++i) {
		dp[i][0]=1;
		dp[0][i]=1;
	}
	for (int i=1; i<=len; ++i) {
		for (int j=1; j<=i; ++j) {
			ll cnt=0;
			for (int k=0; k<=i-1; ++k) {
				for (int l=0; l<=j-1; ++l) {
					cnt=(cnt + dp[k][l] * dp[i-1-k][j-1-l]) % MOD;
				}
			}
			dp[i][j]=(dp[i-1][j] + dp[i][j-1] + cnt) % MOD;
			dp[j][i]=dp[i][j];
		}
	}
}
int main() {
//	freopen("abc.txt", "r", stdin);
	Init();
	ll T;
	cin>>T;
	ll a,b;
//	cout<<T*T*T*T<<endl;
//	for (int i=0; i<=10; i++) {
//		for (int j=0; j<=10; j++) cout<<dp[i][j]<<' ';
//		cout<<endl;
//	}
	while (T--) {
		cin>>a>>b;
		cout<<dp[a][b]<<endl;
	}
	return 0;
}

